package class02;

/**
 * 场景: 希望查询一个数据 L-R 范围内的数据之和
 * 方式一: 定义一个二维数组(表格), 每个(L, R) 对应一个结果, 生成数据慢, 但查询快
 * 方式二: 定义一个一维数组,
 * 每个下标计算从0至当前下标的和; 生成快,节约空间; 但查询完需用 R结果 - (L-1)结果 (L为0时, 直接返回R值)
 */
public class Code01_PreSum {

  public static class RangeSum1 {

    private int[] arr;

    public RangeSum1(int[] array) {
      arr = array;
    }

    public int rangeSum(int L, int R) {
      int sum = 0;
      for (int i = L; i <= R; i++) {
        sum += arr[i];
      }
      return sum;
    }
  }

  public static class RangeSum2 {

    private int[] preSum;

    public RangeSum2(int[] array) {
      int N = array.length;
      preSum = new int[N];
      preSum[0] = array[0];
      for (int i = 1; i < N; i++) {
        preSum[i] = preSum[i - 1] + array[i];
      }
    }

    public int rangeSum(int L, int R) {
      return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
    }
  }
}
